package 题目集.滑动窗口.ch01_定长窗口;

import com.sun.xml.internal.ws.encoding.policy.MtomPolicyMapConfigurator;
import org.junit.Test;

import java.util.BitSet;

/**
 * https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-k/description/
 * 给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。
 */
public class ch02_检查一个字符串是否包含所有长度为K的二进制子串 {

    /**
     * 暴力解：定长窗口遍历原字符串，并将字串放入hash表，最后看hash表的长度是否是2^k次方
     * 因为k<20，所以可以将字符串转为数字放入hash表，这样更快
     *
     * @param s
     * @param k
     * @return
     */
    public boolean hasAllCodes(String s, int k) {
        int total = 1 << k;
        boolean[] bitset = new boolean[total];
        byte[] chars = toByteArray(s.toCharArray());    //将字符串变成01数组
        int mod = (total) - 1;
        int cur = 0;

        for (int i = 0; i < k && i < chars.length; i++) {
            cur = cur << 1 | chars[i];
        }
        bitset[cur] = true;
        int ans = 1;    /*第一个cur一定是不存在的*/
        for (int i = k; i < chars.length; i++) {
            //先左移一位，再加上右侧的那位，移除最左侧（&mod）
            cur = (cur << 1 | chars[i]) & mod;
            if (!bitset[cur]) {
                ans++;
                bitset[cur] = true;
            }
        }
        return ans == total;
    }

    @Test
    public void t1() {
        String s = "101000100011111001110010";
        int k = 3;
        System.out.println(hasAllCodes(s, k));
    }


    /**
     * 将字符串数组变成01数组
     *
     * @param chars
     * @return
     */
    public byte[] toByteArray(char[] chars) {
        byte[] bytes = new byte[chars.length];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = (byte) (chars[i] - '0');
        }
        return bytes;
    }
}
